package LeetCode.leetcode206reverseList;

public class Main {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode head = new ListNode();
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        prin(head);
    }

    //包含数据的链表打印
    public static void prin(ListNode head){
        int sum=0;
        ListNode t = reverseList(head);
        ListNode temp = t.next;
        while (temp != null){
            sum++;
            System.out.printf("%d\t",temp.val);

            temp = temp.next;
        }
        System.out.println();
        System.out.printf("%d\t",sum);
    }
    //不包含数据的链表打印
    public static void prin2(ListNode head){
        ListNode t = reverseList2(head);
        ListNode temp = t;
        while (temp != null){
            System.out.printf("%d\t",temp.val);
            temp = temp.next;
        }
    }

    /**
     * 头插法
     * head不包含数据
     *
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        //如果只有一个节点或者没有节点就直接返回这个链表
        if (head.next == null ||head.next.next ==null)
            return head;
        ListNode cur = head.next;
        ListNode cNext = null;
        //反转链表暂时的头结点
        ListNode reverseHead = new ListNode();
        while (cur != null){
            cNext = cur.next;
            cur.next = reverseHead.next;
            reverseHead.next = cur;
            cur = cNext;
        }
        head = reverseHead;
        return head;
    }

    //head 包含数据

    /**
     * 头插法
     * head 包含数据
     * @param head
     * @return
     */
    public static ListNode reverseList2(ListNode head) {
        //head为空的情况
        if(head == null){
            return head;
        }
        //如果只有一个节点或者没有节点就直接返回这个链表
            if (head.next == null)
                return head;
        ListNode cur = head;
        ListNode cNext = null;
        //反转链表暂时的头结点
        ListNode reverseHead = new ListNode();
            while (cur != null){
                cNext = cur.next;
                cur.next = reverseHead.next;
                reverseHead.next = cur;
                cur = cNext;
            }
        head = reverseHead.next;
        return head;
    }

    /**
     * 双指针法
     * head不包含数据
     * @param head
     * @return
     */
    public static ListNode reverseList3(ListNode head){
        ListNode cur = head;
        ListNode pre = null;
        ListNode temp = null;
        while (cur != null){
            //保存指针
            temp = cur.next;
            //指针反转
            cur.next = pre;
            //指针后移
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}
